Ultraconservative Online Algorithms for Multiclass Problems
Identifieur interne : 001A12 ( Main/Exploration ); précédent : 001A11; suivant : 001A13Ultraconservative Online Algorithms for Multiclass Problems
Auteurs : Koby Crammer [Israël] ; Yoram Singer [Israël]Source :
- Lecture Notes in Computer Science [ 0302-9743 ] ; 2001.
Abstract
Abstract: In this paper we study online classification algorithms for multiclass problems in the mistake bound model. The hypotheses we use maintain one prototype vector per class. Given an input instance, a multiclass hypothesis computes a similarity-score between each prototype and the input instance and then sets the predicted label to be the index of the prototype achieving the highest similarity. To design and analyze the learning algorithms in this paper we introduce the notion of ultraconservativeness. Ultraconservative algorithms are algorithms that update only the prototypes attaining similarity-scores which are higher than the score of the correct label’s prototype. We start by describing a family of additive ultraconservative algorithms where each algorithm in the family updates its prototypes by finding a feasible solution for a set of linear constraints that depend on the instantaneous similarity-scores. We then discuss a specific online algorithm that seeks a set of prototypes which have a small norm. The resulting algorithm, which we term MIRA (for Margin Infused Relaxed Algorithm) is ultraconservative as well. We derive mistake bounds for all the algorithms and provide further analysis of MIRA using a generalized notion of the margin for multiclass problems.
Url:
DOI: 10.1007/3-540-44581-1_7
Affiliations:
Links toward previous steps (curation, corpus...)
- to stream Istex, to step Corpus: 001A43
- to stream Istex, to step Curation: 001936
- to stream Istex, to step Checkpoint: 001066
- to stream Main, to step Merge: 001B05
- to stream Main, to step Curation: 001A12
Le document en format XML
<record><TEI wicri:istexFullTextTei="biblStruct:series"><teiHeader><fileDesc><titleStmt><title xml:lang="en">Ultraconservative Online Algorithms for Multiclass Problems</title><author><name sortKey="Crammer, Koby" sort="Crammer, Koby" uniqKey="Crammer K" first="Koby" last="Crammer">Koby Crammer</name></author><author><name sortKey="Singer, Yoram" sort="Singer, Yoram" uniqKey="Singer Y" first="Yoram" last="Singer">Yoram Singer</name></author></titleStmt><publicationStmt><idno type="wicri:source">ISTEX</idno><idno type="RBID">ISTEX:A31653CA3987CFA1CB3CB611868397EF558D9E22</idno><date when="2001" year="2001">2001</date><idno type="doi">10.1007/3-540-44581-1_7</idno><idno type="url">https://api.istex.fr/document/A31653CA3987CFA1CB3CB611868397EF558D9E22/fulltext/pdf</idno><idno type="wicri:Area/Istex/Corpus">001A43</idno><idno type="wicri:Area/Istex/Curation">001936</idno><idno type="wicri:Area/Istex/Checkpoint">001066</idno><idno type="wicri:doubleKey">0302-9743:2001:Crammer K:ultraconservative:online:algorithms</idno><idno type="wicri:Area/Main/Merge">001B05</idno><idno type="wicri:Area/Main/Curation">001A12</idno><idno type="wicri:Area/Main/Exploration">001A12</idno></publicationStmt><sourceDesc><biblStruct><analytic><title level="a" type="main" xml:lang="en">Ultraconservative Online Algorithms for Multiclass Problems</title><author><name sortKey="Crammer, Koby" sort="Crammer, Koby" uniqKey="Crammer K" first="Koby" last="Crammer">Koby Crammer</name><affiliation wicri:level="1"><country wicri:rule="url">Israël</country></affiliation></author><author><name sortKey="Singer, Yoram" sort="Singer, Yoram" uniqKey="Singer Y" first="Yoram" last="Singer">Yoram Singer</name><affiliation wicri:level="1"><country xml:lang="fr">Israël</country><wicri:regionArea>School of Computer Science & Engineering, The Hebrew University, 91904, Jerusalem</wicri:regionArea><wicri:noRegion>Jerusalem</wicri:noRegion></affiliation><affiliation wicri:level="1"><country wicri:rule="url">Israël</country></affiliation></author></analytic><monogr></monogr><series><title level="s">Lecture Notes in Computer Science</title><imprint><date>2001</date></imprint><idno type="ISSN">0302-9743</idno><idno type="ISSN">0302-9743</idno></series><idno type="istex">A31653CA3987CFA1CB3CB611868397EF558D9E22</idno><idno type="DOI">10.1007/3-540-44581-1_7</idno><idno type="ChapterID">7</idno><idno type="ChapterID">Chap7</idno></biblStruct></sourceDesc><seriesStmt><idno type="ISSN">0302-9743</idno></seriesStmt></fileDesc><profileDesc><textClass></textClass><langUsage><language ident="en">en</language></langUsage></profileDesc></teiHeader><front><div type="abstract" xml:lang="en">Abstract: In this paper we study online classification algorithms for multiclass problems in the mistake bound model. The hypotheses we use maintain one prototype vector per class. Given an input instance, a multiclass hypothesis computes a similarity-score between each prototype and the input instance and then sets the predicted label to be the index of the prototype achieving the highest similarity. To design and analyze the learning algorithms in this paper we introduce the notion of ultraconservativeness. Ultraconservative algorithms are algorithms that update only the prototypes attaining similarity-scores which are higher than the score of the correct label’s prototype. We start by describing a family of additive ultraconservative algorithms where each algorithm in the family updates its prototypes by finding a feasible solution for a set of linear constraints that depend on the instantaneous similarity-scores. We then discuss a specific online algorithm that seeks a set of prototypes which have a small norm. The resulting algorithm, which we term MIRA (for Margin Infused Relaxed Algorithm) is ultraconservative as well. We derive mistake bounds for all the algorithms and provide further analysis of MIRA using a generalized notion of the margin for multiclass problems.</div></front></TEI><affiliations><list><country><li>Israël</li></country></list><tree><country name="Israël"><noRegion><name sortKey="Crammer, Koby" sort="Crammer, Koby" uniqKey="Crammer K" first="Koby" last="Crammer">Koby Crammer</name></noRegion><name sortKey="Singer, Yoram" sort="Singer, Yoram" uniqKey="Singer Y" first="Yoram" last="Singer">Yoram Singer</name><name sortKey="Singer, Yoram" sort="Singer, Yoram" uniqKey="Singer Y" first="Yoram" last="Singer">Yoram Singer</name></country></tree></affiliations></record>Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Ticri/CIDE/explor/OcrV1/Data/Main/Exploration
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 001A12 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Main/Exploration/biblio.hfd -nk 001A12 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien
|wiki= Ticri/CIDE
|area= OcrV1
|flux= Main
|étape= Exploration
|type= RBID
|clé= ISTEX:A31653CA3987CFA1CB3CB611868397EF558D9E22
|texte= Ultraconservative Online Algorithms for Multiclass Problems
}}
| This area was generated with Dilib version V0.6.32. |  |